{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Longest Substring Containing Vowels in Even Counts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheLongestSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个元音包含偶数次的最长子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即&nbsp;&#39;a&#39;，&#39;e&#39;，&#39;i&#39;，&#39;o&#39;，&#39;u&#39; ，在子字符串中都恰好出现了偶数次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;eleetminicoworoep&quot;\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>最长子字符串是 &quot;leetminicowor&quot; ，它包含 <strong>e，i，o</strong>&nbsp;各 2 个，以及 0 个 <strong>a</strong>，<strong>u </strong>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;leetcodeisgreat&quot;\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最长子字符串是 &quot;leetc&quot; ，其中包含 2 个 <strong>e</strong> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;bcbcbc&quot;\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>这个示例中，字符串 &quot;bcbcbc&quot; 本身就是最长的，因为所有的元音 <strong>a，</strong><strong>e，</strong><strong>i，</strong><strong>o，</strong><strong>u</strong> 都出现了 0 次。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 x 10^5</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-longest-substring-containing-vowels-in-even-counts](https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-longest-substring-containing-vowels-in-even-counts](https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"eleetminicoworoep\"', '\"leetcodeisgreat\"', '\"bcbcbc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        presum = {0:-1}\n",
    "        result = 0\n",
    "        pre = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if(c == 'a'):\n",
    "                pre = pre ^ (1 << 0)\n",
    "            elif(c == 'e'):\n",
    "                pre = pre ^ (1 << 1)\n",
    "            elif(c == 'i'):\n",
    "                pre = pre ^ (1 << 2)\n",
    "            elif(c == 'o'):\n",
    "                pre = pre ^ (1 << 3)\n",
    "            elif(c == 'u'):\n",
    "                pre = pre ^ (1 << 4)\n",
    "            else:\n",
    "                pass\n",
    "            if(pre in presum):\n",
    "                result = max(result, i-presum[pre])\n",
    "            else:\n",
    "                presum[pre] = i \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dirc = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}\n",
    "        pos = {0: -1}\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        state = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] in dirc:\n",
    "                state ^= (1 << dirc[s[i]])\n",
    "\n",
    "            if state in pos:\n",
    "                res = max(res, i - pos[state])\n",
    "            else:\n",
    "                pos[state] = i\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mapper = {\n",
    "            'a': 1,\n",
    "            'e': 2,\n",
    "            'i': 4,\n",
    "            'o': 8,\n",
    "            'u': 16\n",
    "        }\n",
    "        dp = {0:-1}\n",
    "        patten = 0\n",
    "        res = 0\n",
    "        for i, c  in enumerate(s):\n",
    "            if c in 'aeiou':\n",
    "                patten ^= mapper[c]\n",
    "            if patten in dp.keys():\n",
    "                res = max(res, i - dp[patten])\n",
    "            else:\n",
    "                dp[patten] = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode id=1371 lang=python3\n",
    "#\n",
    "# [1371] Find the Longest Substring Containing Vowels in Even Counts\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        pos = {0: -1}\n",
    "        cur, ans = 0, 0\n",
    "        for i, ch in enumerate(s):\n",
    "            idx = 'aeiou'.find(ch)\n",
    "            if idx != -1: cur ^= 1 << idx\n",
    "            if cur in pos: ans = max(ans, i - pos[cur])\n",
    "            else: pos[cur] = i\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mask = 0 \n",
    "        mp = {ch:i for i, ch in enumerate(\"aeiou\")}\n",
    "        res = 0\n",
    "        cnt = Counter({0: -1}) \n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in \"aeiou\":\n",
    "                j = mp[ch]\n",
    "                mask = mask ^ (1 << j) \n",
    "            if mask not in cnt:\n",
    "                cnt[mask] = i\n",
    "            res = max(res, i - cnt[mask])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "\t\t\t\t\tn = len(s)\n",
    "\t\t\t\t\t# 只有5个元音字符，状态就5位\n",
    "\t\t\t\t\tmap = [-2] * 32\n",
    "\t\t\t\t\t# map[0...31] = -2\n",
    "\t\t\t\t\t# map[01100] = -2, 这个状态之前没出现过\n",
    "\t\t\t\t\tmap[0] = -1\n",
    "\t\t\t\t\tans = 0\n",
    "\t\t\t\t\tstatus = 0\n",
    "\n",
    "\t\t\t\t\tdef move(char):\n",
    "\t\t\t\t\t\t\t# 元音字符对应的状态转移\n",
    "\t\t\t\t\t\t\treturn {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}.get(char, -1)\n",
    "\n",
    "\t\t\t\t\tfor i in range(n):\n",
    "\t\t\t\t\t\t\t# status : 0....i-1字符串上，aeiou的奇偶性\n",
    "\t\t\t\t\t\t\t# s[i] = 当前字符\n",
    "\t\t\t\t\t\t\t# 情况1 : 当前字符不是元音，status不变\n",
    "\t\t\t\t\t\t\t# 情况2 : 当前字符是元音，a~u(0~4)，修改相应的状态\n",
    "\t\t\t\t\t\t\tm = move(s[i])\n",
    "\t\t\t\t\t\t\tif m != -1:\n",
    "\t\t\t\t\t\t\t\t\tstatus ^= 1 << m\n",
    "\t\t\t\t\t\t\t# status:  0....i字符串上，aeiou的奇偶性\n",
    "\t\t\t\t\t\t\t# 同样的状态，之前最早出现在哪\n",
    "\t\t\t\t\t\t\tif map[status] != -2:\n",
    "\t\t\t\t\t\t\t\t\tans = max(ans, i - map[status])\n",
    "\t\t\t\t\t\t\telse:\n",
    "\t\t\t\t\t\t\t\t\tmap[status] = i\n",
    "\n",
    "\t\t\t\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        def transpose(a):\n",
    "            if a == \"a\":\n",
    "                return 0\n",
    "            elif a == \"e\":\n",
    "                return 1\n",
    "            elif a == \"i\":\n",
    "                return 2\n",
    "            elif a == \"o\":\n",
    "                return 3\n",
    "            elif a == \"u\":\n",
    "                return 4\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        n = len(s)\n",
    "        map = [-2]*32\n",
    "        map[0] = -1\n",
    "        ans = 0\n",
    "        status = 0\n",
    "        for i in range(n):\n",
    "            m = transpose(s[i])\n",
    "            if m!=-1:\n",
    "                status ^= (1<<m)\n",
    "            if map[status] != -2:\n",
    "                ans = max(ans,i-map[status])\n",
    "            else:\n",
    "                map[status] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        first = [-2] * 32\n",
    "        first[0] = -1\n",
    "        mp = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}\n",
    "        pres = 0\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            pres ^= mp.get(ch, 0)\n",
    "            if first[pres] == -2:\n",
    "                first[pres] = i\n",
    "            else:\n",
    "                ans = max(ans, i - first[pres])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        patterns = collections.defaultdict(int)\n",
    "        patterns[0] = -1\n",
    "        pattern  = 0\n",
    "        max_l = 0\n",
    "        for j,i in enumerate(s):\n",
    "            if i == \"a\":\n",
    "                pattern ^= 1<<0\n",
    "            elif i == \"e\":\n",
    "                pattern ^= 1<<1\n",
    "            elif i == \"i\":\n",
    "                pattern ^= 1<<2\n",
    "            elif i == \"o\":\n",
    "                pattern ^= 1<<3\n",
    "            elif i == \"u\":\n",
    "                pattern ^= 1<<4\n",
    "            if pattern in patterns:\n",
    "                max_l = max(max_l,j-patterns[pattern])\n",
    "            else:\n",
    "                patterns[pattern] = j\n",
    "        return max_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}\n",
    "        counts = {0: -1}\n",
    "        bitmask = 0\n",
    "        max_length = 0\n",
    "        \n",
    "        for i, char in enumerate(s):\n",
    "            if char in vowels:\n",
    "                bitmask ^= vowels[char]\n",
    "            \n",
    "            if bitmask not in counts:\n",
    "                counts[bitmask] = i\n",
    "            else:\n",
    "                max_length = max(max_length, i - counts[bitmask])\n",
    "\n",
    "            # print(bitmask)\n",
    "            # print(counts)\n",
    "            # print()\n",
    "        # print(counts)\n",
    "        return max_length\n",
    "\n",
    "\n",
    "        # arr = {}\n",
    "        # result = ''\n",
    "        # vowel_arr = ['a','e', 'i','o','u']\n",
    "        # count = 0\n",
    "        # max_length = 0\n",
    "        # for i in range(len(s)):\n",
    "        #     # result = result + i\n",
    "        #     if s[i] in arr and s[i] in vowel_arr:             \n",
    "        #         count = arr[s[i]] + 1\n",
    "        #         arr[s[i]] = count   \n",
    "        #         if count % 2 != 0:\n",
    "        #             result = result + s[i]\n",
    "        #             max_length\n",
    "        #         else:\n",
    "        #             pass          \n",
    "                    \n",
    "        #     elif s[i] not in arr and s[i] in vowel_arr:\n",
    "        #         arr[s[i]] = 1\n",
    "\n",
    "        # for i in arr:\n",
    "        #     print(i)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        sdict = {\"a\":0, \"e\":0, \"i\":0, \"o\":0, \"u\":0}\n",
    "        ssdict = {\"00000\":-1}\n",
    "        res = 0\n",
    "        for num, i in enumerate(s):\n",
    "            if  i in sdict:\n",
    "                sdict[i] = (sdict[i] + 1)%2\n",
    "            sTemp = \"\".join(map(str, sdict.values()))\n",
    "            # print(sTemp, num)\n",
    "            if sTemp in ssdict:\n",
    "                res = max(res, num - ssdict[sTemp])\n",
    "            else:\n",
    "                ssdict[sTemp] = num\n",
    "        # print(ssdict)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        # vowels={'a','e','i','o','u'}\n",
    "        # seen={0:-1}\n",
    "        # state=0\n",
    "        # result=0\n",
    "        # for i,char in enumerate(s):\n",
    "        #     if char in vowels:\n",
    "        #         state^=1<<(ord(char)-ord('a'))\n",
    "        #         print(state)\n",
    "        #     if state not in seen:\n",
    "        #         seen[state]=i\n",
    "        #     else:\n",
    "        #         result=max(result,i-seen[state])\n",
    "        # return result\n",
    "        # vowels={'a','e','i','o','u'}\n",
    "        # seen={0:-1}\n",
    "        # state=0\n",
    "        # result=0\n",
    "        # for i,char in enumerate(s):\n",
    "        #     if char in vowels:\n",
    "        #         state^=1<<(ord(char)-ord('a'))\n",
    "        #     if state not in seen:\n",
    "        #         seen[state]=i\n",
    "        #     else:\n",
    "        #         result=max(result,i-seen[state])\n",
    "        # return result\n",
    "        vowels={'a','e','i','o','u'}\n",
    "        result=0\n",
    "        state=0\n",
    "        seen={0:-1}\n",
    "        for i,char in enumerate(s):\n",
    "            if char in vowels:\n",
    "                state^=1<<(ord(char)-ord('a'))\n",
    "            if state not in seen:\n",
    "                seen[state]=i\n",
    "            else:\n",
    "                result=max(result,i-seen[state])\n",
    "        return result\n",
    "\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        #五位二进制,经典状态压缩\n",
    "        #位运算+前缀和+贪心(相同状态只保存最靠前的,因为要求子字符串最长)\n",
    "        #不适合用滑窗(因为窗口收缩条件不明确)\n",
    "        mp={\"a\":4,\"e\":3,\"i\":2,\"o\":1,\"u\":0}\n",
    "        pre=dict({0:-1})\n",
    "        mask,ans=0,0\n",
    "        for i,x in enumerate(s):\n",
    "            if x in mp:\n",
    "                mask^=1<<mp[x]\n",
    "            if mask not in pre: pre[mask]=i\n",
    "            else: ans=max(ans,i-pre[mask])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mapper = {\n",
    "            'a': 1,\n",
    "            'e': 2,\n",
    "            'i': 4,\n",
    "            'o': 8,\n",
    "            'u': 16\n",
    "        }\n",
    "        dp = {0:-1}\n",
    "        patten = 0\n",
    "        res = 0\n",
    "        for i, c  in enumerate(s):\n",
    "            if c in mapper.keys():\n",
    "                patten ^= mapper[c]\n",
    "            if patten in dp.keys():\n",
    "                res = max(res, i - dp[patten])\n",
    "            else:\n",
    "                dp[patten] = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        position = [-1] * (1 << 5)\n",
    "        position[0] = 0\n",
    "        curr = 0\n",
    "        ans = 0\n",
    "        # length = 0\n",
    "        # start = 0\n",
    "        # end = 0\n",
    "        for i in range(n):\n",
    "            # curr = 0\n",
    "            if s[i] == 'a': curr ^= 1\n",
    "            elif s[i] == 'e': curr ^= 1 << 1\n",
    "            elif s[i] == 'i': curr ^= 1 << 2\n",
    "            elif s[i] == 'o': curr ^= 1 << 3\n",
    "            elif s[i] == 'u': curr ^= 1 << 4\n",
    "            if position[curr] != -1:\n",
    "                ans = max(ans, i - position[curr] + 1)\n",
    "                # if i - position[curr] > length:\n",
    "                #     length = i - position[curr]\n",
    "                    # start = position[curr]\n",
    "                    # end = i\n",
    "            else: position[curr] = i + 1\n",
    "        # print(position)\n",
    "        # print(s[start : end + 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        m = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}\n",
    "        status = 0\n",
    "        d = {}\n",
    "        d[0] = -1\n",
    "        maxnum = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in m.keys():\n",
    "                status ^= 1 << m[s[i]]\n",
    "                if status in d.keys():\n",
    "                    maxnum = max(maxnum, i-d[status])\n",
    "                else:\n",
    "                    d[status] = i\n",
    "            else:\n",
    "                maxnum = max(maxnum, i-d[status])\n",
    "        if status == 0:\n",
    "            return len(s)\n",
    "        return maxnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        vowels={'a','e','i','o','u'}\n",
    "        seen={0:-1}\n",
    "        state=0\n",
    "        result=0\n",
    "        # for i,char in enumerate(s):\n",
    "        #     if char in vowels:\n",
    "        #         state^=1<<(ord(char)-ord('a'))\n",
    "        #         print(state)\n",
    "        #     if state not in seen:\n",
    "        #         seen[state]=i\n",
    "        #     else:\n",
    "        #         result=max(result,i-seen[state])\n",
    "        # return result\n",
    "        for i,char in enumerate(s):\n",
    "            if char in vowels:\n",
    "                state^=1<<(ord(char)-ord('a'))\n",
    "            if state not in seen:\n",
    "                seen[state]=i\n",
    "            else:\n",
    "                result=max(result,i-seen[state])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        思路: 奇数+奇数=偶数，奇数+偶数=奇数，所以对于 i 位置，只要找到之前最早出现该状态的位置即可，在哈希表里用0表示偶数，1表示奇数；\n",
    "        而这个状态可以用5个位来表示\n",
    "        \"\"\"\n",
    "        yy = ['a', 'e', 'i', 'o', 'u']\n",
    "        mp = [-2] * 32   # 只有5个元音，最大就是31\n",
    "        mp[0] = -1   # 最开始5个字母出现次数都是0，即对应到 -1 的位置\n",
    "        ans = 0\n",
    "        status = 0\n",
    "\n",
    "        def move(c: chr) -> int:\n",
    "            if c in yy:\n",
    "                return yy.index(c)\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            # 当前字符不是元音，状态不变；\n",
    "            # 当前是则改变该字符位的状态，即异或 1 得到\n",
    "            cur = move(s[i])\n",
    "            if cur != -1:\n",
    "                status ^= 1 << cur\n",
    "            # 找到同样的状态最早出现的位置\n",
    "            if mp[status] != -2:\n",
    "                ans = max(ans, i - mp[status])\n",
    "            else:  # 第一次出现\n",
    "                mp[status] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "\t\n",
    "\t\t\t\t\tn = len(s)\n",
    "\t\t\t\t\t# 只有5个元音字符，状态就5位\n",
    "\t\t\t\t\tmap = [-2] * 32\n",
    "\t\t\t\t\t# map[0...31] = -2\n",
    "\t\t\t\t\t# map[01100] = -2, 这个状态之前没出现过\n",
    "\t\t\t\t\tmap[0] = -1\n",
    "\t\t\t\t\tans = 0\n",
    "\t\t\t\t\tstatus = 0\n",
    "\n",
    "\t\t\t\t\tdef move(char):\n",
    "\t\t\t\t\t\t\t# 元音字符对应的状态转移\n",
    "\t\t\t\t\t\t\treturn {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}.get(char, -1)\n",
    "\n",
    "\t\t\t\t\tfor i in range(n):\n",
    "\t\t\t\t\t\t\t# status : 0....i-1字符串上，aeiou的奇偶性\n",
    "\t\t\t\t\t\t\t# s[i] = 当前字符\n",
    "\t\t\t\t\t\t\t# 情况1 : 当前字符不是元音，status不变\n",
    "\t\t\t\t\t\t\t# 情况2 : 当前字符是元音，a~u(0~4)，修改相应的状态\n",
    "\t\t\t\t\t\t\tm = move(s[i])\n",
    "\t\t\t\t\t\t\tif m != -1:\n",
    "\t\t\t\t\t\t\t\t\tstatus ^= 1 << m\n",
    "\t\t\t\t\t\t\t# status:  0....i字符串上，aeiou的奇偶性\n",
    "\t\t\t\t\t\t\t# 同样的状态，之前最早出现在哪\n",
    "\t\t\t\t\t\t\tif map[status] != -2:\n",
    "\t\t\t\t\t\t\t\t\tans = max(ans, i - map[status])\n",
    "\t\t\t\t\t\t\telse:\n",
    "\t\t\t\t\t\t\t\t\tmap[status] = i\n",
    "\n",
    "\t\t\t\t\treturn ans\n",
    "\n",
    "\t\t\t# 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        ans, status, n = 0, 0, len(s)\n",
    "        pos = [-1] * (1 << 5)\n",
    "        pos[0] = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                status ^= 1 << 0\n",
    "            elif s[i] == 'e':\n",
    "                status ^= 1 << 1\n",
    "            elif s[i] == 'i':\n",
    "                status ^= 1 << 2\n",
    "            elif s[i] == 'o':\n",
    "                status ^= 1 << 3\n",
    "            elif s[i] == 'u':\n",
    "                status ^= 1 << 4\n",
    "            if pos[status] != -1:\n",
    "                ans = max(ans, i + 1 - pos[status])\n",
    "            else:\n",
    "                pos[status] = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        presum = {0:-1}\n",
    "        result = 0\n",
    "        pre = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if(c == 'a'):\n",
    "                pre = pre ^ (1 << 0)\n",
    "            elif(c == 'e'):\n",
    "                pre = pre ^ (1 << 1)\n",
    "            elif(c == 'i'):\n",
    "                pre = pre ^ (1 << 2)\n",
    "            elif(c == 'o'):\n",
    "                pre = pre ^ (1 << 3)\n",
    "            elif(c == 'u'):\n",
    "                pre = pre ^ (1 << 4)\n",
    "            if(pre in presum):\n",
    "                result = max(result, i-presum[pre])\n",
    "            else:\n",
    "                presum[pre] = i \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        HashTable = dict()\n",
    "        ans = 0\n",
    "        templist = [0,0,0,0,0]\n",
    "        HashTable[str(templist)] = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"a\":\n",
    "                templist[0] = (templist[0] + 1) %2\n",
    "                pass\n",
    "            elif s[i] == \"e\":\n",
    "                templist[1] = (templist[1] + 1) % 2\n",
    "                pass\n",
    "            elif s[i] == \"i\":\n",
    "                templist[2] = (templist[2] + 1) % 2\n",
    "                pass\n",
    "            elif s[i] == \"o\":\n",
    "                templist[3] = (templist[3] + 1) % 2\n",
    "                pass\n",
    "            elif s[i] == \"u\":\n",
    "                templist[4] = (templist[4] + 1) % 2\n",
    "                pass\n",
    "            if HashTable.get(str(templist),-2) == -2:\n",
    "                HashTable[str(templist)] = i\n",
    "            else:\n",
    "                ans = max(ans,i-HashTable[str(templist)])\n",
    "                # print(i,HashTable[str(templist)],templist)\n",
    "            pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = [-float('inf')] * 32\n",
    "        dp[0] = -1\n",
    "        pattern = 0\n",
    "        res = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'a':\n",
    "                pattern ^= (1 << 0)\n",
    "            elif ch == 'e':\n",
    "                pattern ^= (1 << 1)\n",
    "            elif ch == 'i':\n",
    "                pattern ^= (1 << 2)\n",
    "            elif ch == 'o':\n",
    "                pattern ^= (1 << 3)\n",
    "            elif ch == 'u':\n",
    "\n",
    "                pattern ^= (1 << 4)\n",
    "            if dp[pattern] != -float('inf'):\n",
    "                cur_length = i - dp[pattern]\n",
    "                res = max(res, cur_length)\n",
    "            else:\n",
    "                dp[pattern] = i \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        state = 0\n",
    "        n = len(s)\n",
    "        pos = [inf] * (1<<5)\n",
    "        pos[0] = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                state ^= 1<<0\n",
    "            elif s[i] == 'e':\n",
    "                state ^= 1<<1\n",
    "            elif s[i] == 'i':\n",
    "                state ^= 1<<2\n",
    "            elif s[i] == 'o':\n",
    "                state ^= 1<<3\n",
    "            elif s[i] == 'u':\n",
    "                state ^= 1<<4\n",
    "            \n",
    "            if pos[state] != inf:\n",
    "                ans = max(ans, i-pos[state])\n",
    "            else:\n",
    "                pos[state] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        vowels = ['a', 'e', 'i', 'o', 'u']\n",
    "        dp = [len(s)]*32\n",
    "        dp[0] = -1\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in vowels:\n",
    "                ind = vowels.index(s[i])\n",
    "                cur ^= 1<<ind\n",
    "            if dp[cur]==len(s):\n",
    "                dp[cur] = i\n",
    "            else:\n",
    "                ans = max(ans, i-dp[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        cnt=[-2 for i in range(32)]\n",
    "        cnt[0]=-1\n",
    "        res,state=0,0\n",
    "        str='aeiou'\n",
    "        for i in range(len(s)):\n",
    "            k=str.find(s[i])\n",
    "            if k!=-1:state^=1<<k\n",
    "            if cnt[state]!=-2:res=max(res,i-cnt[state])\n",
    "            else: cnt[state]=i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        l = 0\n",
    "        a = ['a', 'e', 'i', 'o', 'u']\n",
    "        pre = [-inf] * (1 << 5)\n",
    "        ans = 0\n",
    "        status = 0\n",
    "        pre[0] = -1\n",
    "        for i in range(len(s)):\n",
    "            for j in range(5):\n",
    "                if s[i] == a[j]:\n",
    "                    status ^= 1 << j\n",
    "            if pre[status] == -inf:\n",
    "                pre[status] = i\n",
    "            else:\n",
    "                ans = max(ans, i - pre[status])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        ans, status, n = 0, 0, len(s)\n",
    "        pos = [-1] * (1 << 5)\n",
    "        pos[0] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                status ^= 1 << 0\n",
    "            elif s[i] == 'e':\n",
    "                status ^= 1 << 1\n",
    "            elif s[i] == 'i':\n",
    "                status ^= 1 << 2\n",
    "            elif s[i] == 'o':\n",
    "                status ^= 1 << 3\n",
    "            elif s[i] == 'u':\n",
    "                status ^= 1 << 4\n",
    "            if pos[status] != -1:\n",
    "                ans = max(ans, i + 1 - pos[status])\n",
    "            else:\n",
    "                pos[status] = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        a = ['a', 'e', 'i', 'o', 'u']\n",
    "        pre = [-inf] * (1 << 5)\n",
    "        ans = 0\n",
    "        status = 0\n",
    "        pre[0] = -1\n",
    "        for i in range(len(s)):\n",
    "            for j in range(5):\n",
    "                if s[i] == a[j]:\n",
    "                    status ^= 1 << j\n",
    "            if pre[status] == -inf:\n",
    "                pre[status] = i\n",
    "            else:\n",
    "                ans = max(ans, i - pre[status])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        map = [-2] * 32\n",
    "        map[0] = -1\n",
    "        a = e = i = o = u = 0\n",
    "        ans = 0\n",
    "        for j in range(len(s)):\n",
    "            c = s[j]\n",
    "            if c == 'a': a = (a + 1) % 2\n",
    "            if c == 'e': e = (e + 1) % 2\n",
    "            if c == 'i': i = (i + 1) % 2\n",
    "            if c == 'o': o = (o + 1) % 2\n",
    "            if c == 'u': u = (u + 1) % 2\n",
    "            n = a * 1 + e * 2 + i * 4 + o * 8 + u * 16\n",
    "            if map[n] != -2:\n",
    "                ans = max(ans, j - map[n])\n",
    "            else:\n",
    "                map[n] = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mp = {\n",
    "            \"a\":0,\n",
    "            \"e\":1,\n",
    "            \"i\":2,\n",
    "            \"o\":3,\n",
    "            \"u\":4,\n",
    "        }\n",
    "        rs =0\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        ans =0\n",
    "        for i,ch in enumerate(s):\n",
    "            r = i+ 1\n",
    "            if ch in mp:\n",
    "                rs ^= 1<<mp[ch]\n",
    "            if rs in aux:\n",
    "                ans = max(ans,r - aux[rs])\n",
    "            else:\n",
    "                aux[rs] = r\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        status_dict = {}\n",
    "        vowel_dict = {\n",
    "            'a': 0,\n",
    "            'e': 1,\n",
    "            'i': 2,\n",
    "            'o': 3,\n",
    "            'u': 4\n",
    "        }\n",
    "\n",
    "        status_dict[\"00000\"] = -1\n",
    "\n",
    "        len_s = len(s)\n",
    "\n",
    "        cur_status = \"00000\"\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len_s):\n",
    "            cur_ch = s[i]\n",
    "            if cur_ch in vowel_dict:\n",
    "                idx = vowel_dict[cur_ch]\n",
    "                if cur_status[idx] == \"0\":\n",
    "                    cur_status = cur_status[:idx] + \"1\" + cur_status[idx+1:]\n",
    "                else:\n",
    "                    cur_status = cur_status[:idx] + \"0\" + cur_status[idx+1:]\n",
    "            \n",
    "                if cur_status in status_dict:\n",
    "                    res = max(res, i - status_dict[cur_status])\n",
    "                else:\n",
    "                    status_dict[cur_status] = i\n",
    "            else:\n",
    "                res = max(res, i - status_dict[cur_status])\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mapper = {\n",
    "            'a': 1,\n",
    "            'e': 2,\n",
    "            'i': 4,\n",
    "            'o': 8,\n",
    "            'u': 16\n",
    "        }\n",
    "        dp = {0:-1}\n",
    "        patten = 0\n",
    "        res = 0\n",
    "        for i, c  in enumerate(s):\n",
    "            if c in 'aeiou':\n",
    "                patten ^= mapper[c]\n",
    "            if patten in dp.keys():\n",
    "                res = max(res, i - dp[patten])\n",
    "            else:\n",
    "                dp[patten] = i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        d = {0: -1}\n",
    "        cur = ans = 0\n",
    "        tmp = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in tmp:\n",
    "                cur ^= 1 << tmp[ch]\n",
    "            if cur ^ 0 in d:\n",
    "                ans = max(ans, i - d[cur ^ 0])\n",
    "            if cur not in d:\n",
    "                d[cur] = i\n",
    "        # print(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = [-1]*32\n",
    "        patten = 0\n",
    "        res = 0\n",
    "        dp[0] = 0\n",
    "        for i, c  in enumerate(s):\n",
    "            if c == 'a':\n",
    "                patten ^= 1<<0\n",
    "            elif c == 'e':\n",
    "                patten ^= 1<<1\n",
    "            elif c == 'i':\n",
    "                patten ^= 1<<2\n",
    "            elif c == 'o':\n",
    "                patten ^= 1<<3\n",
    "            elif c == 'u':\n",
    "                patten ^= 1<<4\n",
    "            if dp[patten] != -1:\n",
    "                res = max(res, i + 1 - dp[patten])\n",
    "            else:\n",
    "                dp[patten] = i + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        # bit_mask由左至右对应 aeiou 5个元音字母的出现次数的奇偶性，\n",
    "        # 1代表某个字母出现奇数次，0代表出现偶数次\n",
    "        bit_mask = eval('0b00000')\n",
    "        # 下面一行，初始化状态集，一开始元音字母都是0次(都为偶数)，这种情况发生在-1位置，即0位置的左侧\n",
    "        # state_first_idx的含义为，某种状态(key)：第一次出现的位置(index)\n",
    "        state_first_idx = {eval('0b00000'): -1}\n",
    "        vowels = 'aeiou'\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if (idx := vowels.find(s[i])) > -1:  # str的find方法，找不到返回-1，找到返回元素在字符串中的index，将找到的结果放在idx中\n",
    "                bit_mask ^= eval('0b10000') >> idx  # 找到idx后，就要将对应位置进行翻转(用异或实现)\n",
    "                                                    # eval('0b10000') >> idx，就是将找到的元音所对应的那位设为1，\n",
    "                                                    # 它再和原始的 bit_mask 异或就实现了将元音对应位置翻转\n",
    "            if bit_mask not in state_first_idx:  # 如果当前状态没有出现，则将其记录\n",
    "                state_first_idx[bit_mask] = i\n",
    "            ans = max(ans, i - state_first_idx[bit_mask])  # 更新结果\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        num = 0\n",
    "        for i in range(len(s)):\n",
    "            c2n = {'a': 0, 'e': 0, 'i': 0, 'o':0, 'u': 0}\n",
    "            if num >= len(s[i:]):\n",
    "                break\n",
    "            for j, c in enumerate(s[i:]):\n",
    "                if c in c2n:\n",
    "                    c2n[c] = (c2n[c] + 1) % 2\n",
    "                if sum(c2n.values()) == 0:\n",
    "                    num = max(num, j+1)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mp = {}\n",
    "        for i,x in enumerate('aeiou'):\n",
    "            mp[x] = i\n",
    "\n",
    "        pre = {0:0}\n",
    "        xor = 0\n",
    "        ans = 0\n",
    "        for i,x in enumerate(s, 1):\n",
    "            if x in mp:\n",
    "                bit = 1 << mp[x]\n",
    "                xor ^= bit\n",
    "            if xor in pre:\n",
    "                ans = max(ans, i-pre[xor])\n",
    "            else:\n",
    "                pre[xor] = i\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        def transpose(i):\n",
    "            if i==\"a\":\n",
    "                return 0\n",
    "            if i==\"e\":\n",
    "                return 1\n",
    "            if i==\"o\":\n",
    "                return 2\n",
    "            if i==\"u\":\n",
    "                return 3\n",
    "            if i==\"i\":\n",
    "                return 4\n",
    "            else:\n",
    "                return -1\n",
    "        n = len(s)\n",
    "        map = [-2]*32\n",
    "        map[0] = -1\n",
    "        status = 0\n",
    "        ans = 0\n",
    "      \n",
    "        for i in range(n):\n",
    "            a = transpose(s[i])\n",
    "            if a!=-1:\n",
    "                status = status^(1<<a)\n",
    "            if map[status]!=-2:\n",
    "                ans = max(ans,i-map[status])\n",
    "            else:\n",
    "                map[status] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        def cll(k):\n",
    "            if k == 'a':\n",
    "                return 0\n",
    "            if k == 'e':\n",
    "                return 1\n",
    "            if k == 'i':\n",
    "                return 2\n",
    "            if k == 'o':\n",
    "                return 3\n",
    "            if k == 'u':\n",
    "                return 4\n",
    "            return -1\n",
    "        arr = [-2 for _ in range(32)]\n",
    "        arr[0] = -1\n",
    "        status = 0\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            m = cll(s[i])\n",
    "            if m != -1:\n",
    "                status ^= 1 << m\n",
    "            if arr[status] == -2:\n",
    "                arr[status] = i\n",
    "            else:\n",
    "                ans = max(ans, i - arr[status])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "def I():\n",
    "    return input()\n",
    "\n",
    "def II():\n",
    "    return int(input())\n",
    " \n",
    "def MII():\n",
    "    return map(int, input().split())\n",
    " \n",
    "def LI():\n",
    "    return list(input().split())\n",
    " \n",
    "def LII():\n",
    "    return list(map(int, input().split()))\n",
    " \n",
    "def GMI():\n",
    "    return map(lambda x: int(x) - 1, input().split())\n",
    " \n",
    "def LGMI():\n",
    "    return list(map(lambda x: int(x) - 1, input().split()))\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        mp = DefaultDict(int)\n",
    "        a,e,i,o,u = 0,0,0,0,0\n",
    "        mp[0] = -1\n",
    "        ans = 0\n",
    "        for d,c in enumerate(s):\n",
    "            if c == 'a':\n",
    "                a ^= 1\n",
    "            elif c == 'e':\n",
    "                e ^= 1\n",
    "            elif c == 'i':\n",
    "                i ^= 1\n",
    "            elif c == 'o':\n",
    "                o ^= 1\n",
    "            elif c == 'u':\n",
    "                u ^= 1\n",
    "            cur = a << 4 | e << 3 | i << 2 | o << 1 | u\n",
    "            for j in range(1 << 5):\n",
    "                if j in mp and cur ^ j == 0:\n",
    "                    ans = max(ans, d - mp[j])\n",
    "            mp.setdefault(cur, d)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        state = 0\n",
    "        mem = {0:-1}\n",
    "        curmax = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == \"a\":\n",
    "                state = state^1\n",
    "            elif s[i] == \"e\":\n",
    "                state = state^2 \n",
    "            elif s[i] == \"i\":\n",
    "                state = state^4\n",
    "            elif s[i] == \"o\":\n",
    "                state = state^8\n",
    "            elif s[i] == \"u\":\n",
    "                state = state^16\n",
    "\n",
    "            if state in mem:\n",
    "                curmax = max(curmax, i-mem[state])\n",
    "                # print(s[mem[state]+1:i+1], len(s[mem[state]+1:i+1]))\n",
    "            else:\n",
    "                mem[state] = i\n",
    "        return curmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = [-float('inf')]*32\n",
    "        dp[0]=-1\n",
    "        n = len(s)\n",
    "        pattern = 0\n",
    "        max_len = 0\n",
    "        for i in range(n):\n",
    "            if s[i]=='a':\n",
    "                pattern^=1<<0\n",
    "            elif s[i]=='e':\n",
    "                pattern^=1<<1\n",
    "            elif s[i]=='i':\n",
    "                pattern^=1<<2\n",
    "            elif s[i]=='o':\n",
    "                pattern^=1<<3\n",
    "            elif s[i]=='u':\n",
    "                pattern^=1<<4\n",
    "            \n",
    "            if dp[pattern]!=-float('inf'):\n",
    "                idx = dp[pattern]\n",
    "                max_len = max(max_len,i-idx)\n",
    "            else:\n",
    "                dp[pattern]=i\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        aeiou = {\"a\": 1, \"e\": 2, \"i\": 4, \"o\": 8, \"u\": 16}\n",
    "        counter = {0: -1}\n",
    "        result = 0\n",
    "        bit = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c in aeiou:\n",
    "                bit ^= aeiou[c]\n",
    "            if bit not in counter:\n",
    "                counter[bit] = i\n",
    "            else:\n",
    "                result = max(result, i - counter[bit])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        k={'a':0,'e':1,'i':2,'o':3,'u':4}\n",
    "        states={}\n",
    "        states[0]=-1\n",
    "        now=0\n",
    "        res=0\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch in k:\n",
    "                now^=1<<k[ch]\n",
    "            if now not in states:\n",
    "                states[now]=i\n",
    "            res=max(res,i-states[now])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        pre = dict()\n",
    "        cnt = [0]*5\n",
    "        ind = {w: i for i, w in enumerate(\"aeiou\")}\n",
    "        pre[(0, 0, 0, 0, 0)] = -1\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] in ind:\n",
    "                cnt[ind[s[i]]] += 1\n",
    "                cnt[ind[s[i]]] %= 2\n",
    "            if tuple(cnt) in pre:\n",
    "                if i-pre[tuple(cnt)] > ans:\n",
    "                    ans = i - pre[tuple(cnt)]\n",
    "            else:\n",
    "                pre[tuple(cnt)] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dic={0:-1}\n",
    "        ans=0\n",
    "        presum=0\n",
    "        for i,c in enumerate(s):\n",
    "            cur=1\n",
    "            if c=='a':\n",
    "                cur=cur<<1\n",
    "            elif c=='e':\n",
    "                cur=cur<<2\n",
    "            elif c=='i':\n",
    "                cur=cur<<3\n",
    "            elif c=='o':\n",
    "                cur=cur<<4\n",
    "            elif c=='u':\n",
    "                cur=cur<<5\n",
    "            if cur>1: presum^=cur\n",
    "            if presum not in dic:\n",
    "                dic[presum]=i\n",
    "            else:\n",
    "                ans=max(ans,i-dic[presum])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        hashtable = {0:-1}\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                cur = cur^1\n",
    "            if s[i] == 'e':\n",
    "                cur = cur^2\n",
    "            if s[i] == 'i':\n",
    "                cur = cur^4\n",
    "            if s[i] == 'o':\n",
    "                cur = cur^8\n",
    "            if s[i] == 'u':\n",
    "                cur = cur^16\n",
    "            if cur==0:\n",
    "                ans = max(ans, i+1)\n",
    "            if cur in hashtable:\n",
    "                ans = max(ans, i-hashtable[cur])\n",
    "            if cur not in hashtable:\n",
    "                hashtable[cur] = i\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        pre, res = 0, 0\n",
    "        pos = {0: -1}\n",
    "        idx = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in idx:\n",
    "                pre ^= (1 << idx[s[i]])\n",
    "            if pre in pos:\n",
    "                res = max(res, i - pos[pre])\n",
    "            else:\n",
    "                pos[pre] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        x, res = 0, 0\n",
    "        p = {}\n",
    "        p[0] = -1\n",
    "\n",
    "        for i, e in enumerate(s):\n",
    "            if e in 'aeiou':\n",
    "                if e == 'a': x ^= 1 << 4\n",
    "                elif e == 'e': x ^= 1 << 3\n",
    "                elif e == 'i': x ^= 1 << 2\n",
    "                elif e == 'o': x ^= 1 << 1\n",
    "                else: x ^= 1\n",
    "            if x not in p:\n",
    "                p[x] = i\n",
    "                if x == 0: res = i + 1\n",
    "            elif i - p[x] > res:\n",
    "                res = i - p[x]\n",
    "            \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        posDict = [-1] * (1<<5)\n",
    "        posDict[0] = 0\n",
    "        status = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                status ^= 1<<0\n",
    "            elif s[i] == 'e':\n",
    "                status ^= 1<<1\n",
    "            elif s[i] == 'i':\n",
    "                status ^= 1<<2\n",
    "            elif s[i] == 'o':\n",
    "                status ^= 1<<3\n",
    "            elif s[i] == 'u':\n",
    "                status ^= 1<<4\n",
    "            if posDict[status] != -1:\n",
    "                res = max(res, i+1-posDict[status])\n",
    "            else:\n",
    "                posDict[status] = i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        m = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}\n",
    "        status = 0\n",
    "        d = [-2]*32\n",
    "        d[0] = -1\n",
    "        maxnum = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in m.keys():\n",
    "                status ^= 1 << m[s[i]]\n",
    "                if d[status] != -2:\n",
    "                    maxnum = max(maxnum, i-d[status])\n",
    "                else:\n",
    "                    d[status] = i\n",
    "            else:\n",
    "                maxnum = max(maxnum, i-d[status])\n",
    "        # if status == 0:\n",
    "        #     return len(s)\n",
    "        return maxnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        alphbet = ['a','e','i','o','u']\n",
    "        dic = {}\n",
    "        dic[0b00000]=-1\n",
    "        count = 0b00000\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in alphbet:\n",
    "                count ^= 0b00001<<alphbet.index(s[i])\n",
    "            if count in dic:\n",
    "                ans = max(ans,i-dic[count])\n",
    "            else:\n",
    "                dic[count]=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = {0:-1}\n",
    "        ad = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            idx = 'aeiou'.find(c)\n",
    "            if idx != -1:\n",
    "                ad ^= 1 << idx\n",
    "            if ad in dp:\n",
    "                ans = max(ans, i-dp[ad])\n",
    "            else:\n",
    "                dp[ad] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = [-float('inf')]*32\n",
    "        dp[0] = -1\n",
    "        pattern = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                pattern^= (1<<0)\n",
    "            elif s[i] == 'e':\n",
    "                pattern^= (1<<1)\n",
    "            elif s[i] == 'i':\n",
    "                pattern^= (1<<2)\n",
    "            elif s[i] == 'o':\n",
    "                pattern^= (1<<3)\n",
    "            elif s[i] == 'u':\n",
    "                pattern^= (1<<4)\n",
    "            if dp[pattern] != -float('inf'):\n",
    "                cur_len = i-dp[pattern]\n",
    "                res = max(res,cur_len)\n",
    "            else:\n",
    "                dp[pattern] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        k={'a':0,'e':1,'i':2,'o':3,'u':4}\n",
    "        states={}\n",
    "        now,res,states[0]=0,0,-1\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch in k:\n",
    "                now^=1<<k[ch]\n",
    "            if now not in states:\n",
    "                states[now]=i\n",
    "            res=max(res,i-states[now])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        hashtable = {0:-1}\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                cur = cur^1\n",
    "            elif s[i] == 'e':\n",
    "                cur = cur^2\n",
    "            elif s[i] == 'i':\n",
    "                cur = cur^4\n",
    "            elif s[i] == 'o':\n",
    "                cur = cur^8\n",
    "            elif s[i] == 'u':\n",
    "                cur = cur^16\n",
    "            if cur==0:\n",
    "                ans = max(ans, i+1)\n",
    "            elif cur in hashtable:\n",
    "                ans = max(ans, i-hashtable[cur])\n",
    "            if cur not in hashtable:\n",
    "                hashtable[cur] = i\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        dp = [float('-inf')] * 32\n",
    "\n",
    "        dp[0] = -1\n",
    "        pattern = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                pattern ^= (1 << 0)\n",
    "            elif s[i] == 'e':\n",
    "                pattern ^= (1 << 1)\n",
    "            elif s[i] == 'i':\n",
    "                pattern ^= (1 << 2)\n",
    "            elif s[i] == 'o':\n",
    "                pattern ^= (1 << 3)\n",
    "            elif s[i] == 'u':\n",
    "                pattern ^= (1 << 4)\n",
    "            if dp[pattern] != -float('inf'):\n",
    "                tmplen = i - dp[pattern]\n",
    "                res = max(res, tmplen)\n",
    "            else:\n",
    "                dp[pattern] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        d ={}\n",
    "        d[0] = -1\n",
    "        currSum = 0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            sub = s[i]\n",
    "            left = -1\n",
    "            if sub == 'a':\n",
    "                left = 0\n",
    "            elif sub == 'e':\n",
    "                left = 1\n",
    "            elif sub == 'i':\n",
    "                left = 2\n",
    "            elif sub == 'o':\n",
    "                left = 3\n",
    "            elif sub == 'u':\n",
    "                left = 4\n",
    "            if left >=0:\n",
    "                currSum ^= (1<<left)\n",
    "\n",
    "            if currSum in d:\n",
    "                ans = max(i - d[currSum],ans)\n",
    "            else:\n",
    "                d[currSum] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        first = [-2] * 32\n",
    "        first[0] = -1\n",
    "        pres = 0\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'a':\n",
    "                pres ^= 1\n",
    "            elif ch == 'e':\n",
    "                pres ^= 2\n",
    "            elif ch == 'i':\n",
    "                pres ^= 4\n",
    "            elif ch == 'o':\n",
    "                pres ^= 8\n",
    "            elif ch == 'u':\n",
    "                pres ^= 16\n",
    "            if first[pres] == -2:\n",
    "                first[pres] = i\n",
    "            else:\n",
    "                if (tmp := i - first[pres]) > ans:\n",
    "                    ans = tmp\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        vowels = \"aeiou\"\n",
    "        vowels_map = {vowel: i for i, vowel in enumerate(vowels)}\n",
    "        \n",
    "        # 初始状态：每个元音字母都出现了偶数次\n",
    "        state = [0, 0, 0, 0, 0]\n",
    "        state_map = {tuple(state): -1}\n",
    "        \n",
    "        max_length = 0\n",
    "        current_state = state.copy()\n",
    "        \n",
    "        for i, char in enumerate(s):\n",
    "            if char in vowels:\n",
    "                current_state[vowels_map[char]] ^= 1\n",
    "            \n",
    "            if tuple(current_state) in state_map:\n",
    "                max_length = max(max_length, i - state_map[tuple(current_state)])\n",
    "            else:\n",
    "                state_map[tuple(current_state)] = i\n",
    "        \n",
    "        return max_length\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        D={}\n",
    "        cur=set()\n",
    "        cur_val=0\n",
    "        tar={\"a\":1,\"e\":10,\"i\":100,\"o\":1000,\"u\":10000}\n",
    "        D[cur_val]=0\n",
    "        now_max=0\n",
    "        print(\"\".join(cur))\n",
    "        for ind,i in enumerate(s):\n",
    "            if(i in tar):\n",
    "                if(i in cur):\n",
    "                    cur_val-=tar[i]\n",
    "                    cur.discard(i)\n",
    "                else:\n",
    "                    cur_val+=tar[i]\n",
    "                    cur.add(i)\n",
    "            if(cur_val in D):\n",
    "                #print(ind,D[\"\".join(cur)])\n",
    "                now_max=max(now_max,ind-D[cur_val]+1)\n",
    "            else:\n",
    "                D[cur_val]=ind+1\n",
    "        print(D)\n",
    "        return now_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheLongestSubstring(self, s: str) -> int:\n",
    "        # 最长子串问题，要么滑窗，要么dp（哈希）\n",
    "        f = dict(zip('aeiou', range(5)))\n",
    "        d = defaultdict(lambda: inf)\n",
    "        d[0] = -1\n",
    "        ps = res = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in 'aeiou':\n",
    "                ps ^= 1 << f[s[i]]\n",
    "                d[ps] = min(d[ps], i)\n",
    "            res = max(res, i - d[ps])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
